#include <papi.h>
#include "scan.h"
#include "reduce.h"
#include "limits.h"

pthread_mutex_t lock;
pthread_barrier_t barrier;

class Tally {
public:
  int* count;
  const Tally operator+(const Tally &other) const;
  const Tally operator=(const Tally &rhs);
  Tally() {};
  Tally(Tally const& t) {
    count = new int[INPUT_RANGE];
    for(INDEX i=0; i<INPUT_RANGE; i++)
      count[i]=t.count[i];
  }
  ~Tally();
};

const Tally Tally::operator+(const Tally &other) const {
  Tally result;
  result.count = new int[INPUT_RANGE];
  for(INDEX i=0; i<INPUT_RANGE; i++)
    result.count[i] = this->count[i]+other.count[i];
  return result;
}

const Tally Tally::operator=(const Tally &rhs) {
  for(INDEX i=0; i<INPUT_RANGE; i++) {
    this->count[i] = rhs.count[i];
  }
  return *this;
}

Tally::~Tally() {
  delete [] count;
}

class SortReducer: public Reducer<int, Tally>
{
public:
  void init(Tally& t) {
    t.count = new int[INPUT_RANGE];
    for(INDEX i=0; i<INPUT_RANGE; i++)
      t.count[i] = 0;
  }
  void accum(Tally& t, int d) {t.count[d]++;}
  void combine(Tally& left, Tally right) { left=left+right;}
  Tally reduce(Tally t) { return t;}
  SortReducer(int* data, INDEX length)
    : Reducer<int, Tally>(data, length) {}
};

class SortScanner: public Scanner<int, int>
{
public:
  int init() { return 0;}
  int accum(int t, int d) { return t+d;}
  int combine(int left, int right) { return left+right;}
  int scan(int t, int not_used) { return t;}
  SortScanner(int* data, int* result, INDEX length)
    : Scanner<int, int>(data, result, length) {}
};

int main() {
  int* data = (int*) new int [INPUT_SIZE];
  int* result = (int*) new int [INPUT_SIZE];
  int* histogram;
  int* starting_index = (int*) new int [INPUT_RANGE+1];

  cout<<INPUT_SIZE<<" "<<INPUT_RANGE<<endl;

  // initialize PAPI library
  unsigned long chkflg = PAPI_VER_CURRENT;
  PAPI_library_init(chkflg);
  if (chkflg != PAPI_VER_CURRENT) {
    cout<<"Error PAPI Library out of date"<<endl;
    exit(1);
  }

  // generate the input randomly
  for(INDEX i=0; i<INPUT_SIZE; i++)
    data[i] = rand()%INPUT_RANGE;

  // initialize data structure
  starting_index[0] = 0;

  // start timing
  long long start = PAPI_get_real_usec();

  // calculate the historgram
  SortReducer reducer(data, INPUT_SIZE);
  reducer.Start();
  histogram = reducer.result.count;

  // calculate the start index for each key
  SortScanner scanner(histogram, starting_index+1, INPUT_RANGE);
  scanner.Start();

  // sort input data;
  for(INDEX i=0; i<INPUT_SIZE; i++) {
    result[starting_index[data[i]]] = data[i];
    starting_index[data[i]] ++;
  }

  // end timing
  long long end = PAPI_get_real_usec();

  cout<<"time in ms: "<<end - start<<endl;
  cout<<"checking results"<<endl;

  // check result
  for(INDEX i=0; i<INPUT_SIZE; i++) {
    bool f = 0;
    INDEX j;
    for(j=0; j<INPUT_SIZE; j++) {
      if(data[j] == result[i]) {
        f = 1;
        break;
      }
    }
    if (f!=1) {
      //cout<<result[i]<<" "<<i<<endl;
      assert(f==1);
    }
    if(i>0)
      assert(result[i]>=result[i-1]);
    //cout<<result[i]<<" ";
  }

  cout<<endl<<"sort succeeded"<<endl;

  pthread_exit(NULL);
}
